©作者 | 黄春喜
单位 | 香港科技大学
研究方向 | 智能交通
摘要
根据时间序列本身的不同特点，时间序列相似度的衡量（时间序列间距离的度量）存在多种方法。本文从欧氏距离出发，进一步延伸至 Dynamic Time Warping（DTW）、一些 DTW 存在的缺点和相关的解决办法以及 DTW 的两个变种 Derivative Dynamic Time Warping（DDTW）和 Weighted Dynamic Time Warping（WDTW）。
前言/背景
在众多广泛的科研领域中，时间序列是一种无处不在的数据格式。对于时间序列相关的研究而言，其中一种最常见的需求就是比较两个时间序列是否相似。有效地比较时间序列间的相似度在很多科学/工程任务中非常必要且关键，如：分类/聚类/语音识别/步态识别等。 以某个生产制造环节中针对产成品某项（些）特征所收集到的时间序列数据为例。首先，所收集到的代表良品和次品的时序数据中在某些特定特征上有区别，且这些区别具有与领域知识相关的特定物理含义；其次，由于生产制造过程中的本身特性，所收集到的时序数据长度是不相等的；再而言，次品的产生存在多种原因，换句话说，产成品不只可以进行二分类成良品和次品两个种类，而是可以进一步区分为良品、次品种类 1、次品种类 2、次品种类 3 等多种类；最后，跟很多实际生产制造中的数据一样，良品数据量远大于次品数据量，次品继续细分的各种类次品数据更是少之甚少，整体存在严重的数据不平衡问题。 为了在正常生产制造过程中实现良品和不同种次品的多分类任务，比较所收集到的时间序列间的相似度是重要的一步。从直觉上不难理解，比较时间序列的相似度等同于计算时间序列间的“距离”，两个时间序列之间的“距离”越大，二者的相似度则越小，反之同理。 故本文基于此从欧氏距离出发，进一步延伸至 Dynamic Time Warping（DTW）、一些 DTW 的缺点和相关的解决办法以及 DTW 的两个变种 Derivative Dynamic Time Warping（DDTW）和 Weighted Dynamic Time Warping（WDTW）。鉴于关于 DTW 的细节已经有很多优质博文介绍，故本文只阐述基本概念、更多关注不同方法间的区别、过渡的逻辑以及不同方法所适用的问题。
欧氏距离
提到衡量时间序列之间的距离，欧氏距离（Euclidean Distance）是最直接的方法，它概念简单，在此不赘述。当应用欧氏距离来比较两个时间序列时，序列与序列之间的每一个点按顺序建立起了一对一的对应关系，根据点与点之间的对应关系计算其欧氏距离作为两个时间序列之间的距离度量（相似度）。如下图 1 所示：
在应用欧氏距离时，第一个时间序列中的第 i 个点分别与第二个时间序列中的第 i 个点形成一一对应。然而，欧氏距离在某些情况下会出现问题，如下图 2 所示：
▲ 图2. 两个不等长时间序列间的欧氏距离是否可行？ 当两个时间序列的长度不相等时，较长的一个时间序列总会剩下无法被匹配到的点，这种情况如何计算欧氏距离？毫无疑问，此时欧氏距离不再可行。此外，如图 1 中红圈所示，两个时间序列在时间轴上有一定的平移但总体的趋势是相似的，自然地，当我们想人为对齐图1中两个时间序列时，红圈中的两个向下凸起的点应该相互对应起来。很显然，欧氏距离的这种方式按顺序点对点的方法无法满足我们的需求。 综上，在时间序列间的距离度量上，欧氏距离有以下限制：（1）只适用于处理等长的时间序列；（2）在将时间序列对齐时无法考虑 X 轴上的变化，导致有时对齐出现不自然。
特别地，作为一种常见的标准距离度量，欧氏距离是另一种更为广泛的距离度量——闵式距离（Minkowski distance）当 p 取值为 2 时的特例。闵式距离中 p=1 时和 p=infinity 时，分别对应曼哈顿距离和两个时间序列点与点之间距离差值的最大值。
DTW (Dynamic Time Warping)
针对上文提到的欧氏距离无法处理不等长数据、处理等长数据时对齐不自然的两个主要问题，为了解决不等长数据的距离度量和匹配问题，上世纪 70 年代，日本学者 Itakura 等人提出了 DTW。在过去的几十年里，DTW 已经被广泛应用于孤立词语音识别、手势识别、数据挖掘和信息检索等场景中，DTW 一度是语音识别的主流方法。DTW 的原理此处简述如下： 对于两个不等长的时间序列 Q 和 C，长度分别为 n 和 m：
要使用 DTW 来对齐两个不等长的时间序列，需要构建一个 n*m 的距离矩阵，矩阵中的第 i 行第 j 列所对应的元素代表的就是序列中点 。可参见下图 3：
▲ 图3. DTW中的warping path示意图 上图所示为 n*m 的矩阵，每一个方格代表矩阵中的每一个元素。对于两个时间序列而言，DTW 抛开了欧氏距离的限制，其本意是要寻找到一个连续的包含两个时间序列中所有点互相对应的一个匹配关系（这种匹配可以是第 ），这些匹配关系的集合共同构成了图 3 中的黑色实线 warping path W：
要进行 DTW 匹配，warping path W 需满足以下条件： 1-边界性（Boundary conditions）： ，简而言之，两个经 DTW 对齐的时间序列应该首对首、尾对尾相连，反映到距离矩阵中就是 warping path 应从一个角落出发、在对角线方向上的另一个角落停止。 2-连续性（Continuity）： 每次 warping path 向下一步移动必须是连续的，反映到距离矩阵中就是下一步只能在原方格的相邻方格中选取（方向需满足对角线方向）。数学上可写成：对于 。 3-单调性（Monotonicity）： 两个时间序列间的对应必须按照顺序进行，warping path不能有交叉。数学上可写成： 。 满足这些条件的 W 还是有很多个，DTW 只寻找能够最小化 warping cost 的 W：
在上式中，K 是 warping path 的长度，除以 K 可以消除不同长度的 warping path 的影响。 最终，两个不等长时序数据的对应关系可以通过动态规划来求解以下递归式得到：
其中， 列时所积累的 warping path 的总距离。
DTW面临的问题及其解决方案
尽管 DTW 已经被成功应用到很多领域中，DTW 依然存在缺点：有时 DTW 会在对齐时产生不自然的扭曲/翘曲。如下图 4 所示：
▲ 图4. 合成数据中DTW在对齐时产生的Singularities A 中实线、虚线所展示的是两条合成信号（均值、方差都相同），B 中展示的是自然的“feature to feature”的对应，而 C 中展示的则是 DTW 的结果。不难发现，DTW 没能自然地将图形中的波峰与波峰相对应，反而产生了一个序列中的一个点对应另外一个序列中的多个点的情况，这种情况被称为“Singularities”。出现这种情况的原因是 DTW 算法试图通过扭曲 X 轴来解释 Y 轴上的变化。 为了解决“Singularities”问题，过去的研究提出了很多方案，大致可归为以下三类： 1-Windowing： 归根结底，出现 singularities 就是因为两个时间序列上相隔很远的点仅因为值相同/相近容易被 warping 到一起。可以限制 DTW 在 warping 过程中的能选择的范围来解决 singularities，具体可以通过设置一个 warping window 来实现，故称之为 Windowing方法。数学上可写作： 作为 window width 是一个正整数。图 3 中两虚线所夹范围即为经 window 限制后的范围，此时 warping path 就只能在此区域内。 2-Slope weighting： 当传统 DTW 中的递归式改为下式时，即可实现 slope weighting。
不难发现，唯一的区别在于在 min 函数中的后两项前加了 X ，X 为一个正实数。当对 X 的值进行调整时，可以使得 warping path 的方向（slope）会有一定的调整。 X 取较大值时，warping path 的选择会更多的朝向对角线方向。 3-Step patterns： 改变传统 DTW 中的递归式为下式可以实现改变 warping path step。
将传统 DTW 中的递归式和上式分别可视化如下图 5 中 A、B 所示：
▲ 图5. 两种不同step pattern的递归式的可视化 A 所对应的即为传统 DTW 的递归式，下一步只能在距离矩阵中相邻的三个方格中选取，而 B 中所对应的就是改变了 step 后的递归式。相较于 A 中，B 中对于每一个第一步没有沿着对角线方向走的方格都再朝其所在方格的对角线方向移动一步，这样即可实现改变 step pattern。 总的来说，以上三类解决方案在一定程度上对解决 singularities 有一定帮助，然而，它们仍然存在以下缺点： （1）有可能错过正确的 warping path。以上三类方法都是在没有任何前提条件的情况下人为地对 warping path 进行限制和调整来减少翘曲，这很有可能会错过真正正确的 warping path。 （2）参数的选择没有明确的指导。在 Windowing 方法中 R 值的选取、Slope weighting 方法中 X 都是人为视具体场景主观调整、没有明确标准的。
Derivative Dynamic Time Warping (DDTW)
实际上，DTW 之所以造成“Singularities”，本质上是由于 DTW 算法本身所考虑的特征决定的：DTW 算法只考虑数据点在 Y 轴上的值。 例如：两个数据点 位于一个时间序列的下降趋势部分。对于 DTW 而言，很容易将这两个点匹配在一起，因为它们的值相同。然而，从直觉上来说，我们很难把两个趋势相反的部分匹配在一起。为了避免 DTW 只考虑 Y 轴的值造成“Singularities”问题， DDTW 出现了。 DDTW 不考虑数据点的 Y 轴的值，而是考虑更高层次的特征——时序数据的“形状”。该方法通过计算时序数据的一阶导数来获取与“形状”相关的信息，所以被称为 Derivative DTW。 DDTW 本身的概念也很简单，对于传统 DTW 而言，距离矩阵中的元素即为两个点 之间的距离；然而对于 DDTW 而言，此时的“距离矩阵”中的元素不再是两点之间的距离，而是时序数据在两点处一阶导数的差值的平方。尽管有多种方法估计一阶导数，出于简便和拓展性，DDTW 中的一阶导数估计采用以下方法：
不难发现，在 点处一阶导数的估计就是通过该点和该点左边点的直线斜率与通过该点左边点和该点右边点的直线斜率的平均数。Keogh, E. J., & Pazzani, M. J. 提到，在只考虑两个数据点的情况下，这种估计方法面对 outliers 更为稳定。 需要注意的是，这种一阶导数的估计方法无法计算时序数据的第一个数据点和最后一个数据点的一阶导数，在实际操作时可以用第二个数据点和倒数第二个数据点的导数来替代。此外，对于高噪声的数据集可以在估计一阶导数之前先做 exponential smoothing。
Weighted Dynamic Time Warping (WDTW)
上文提到，经典的 DTW 算法在匹配两个时间序列上的点时仅考虑 Y 轴上的值，而不考虑所匹配的点在 X 轴上的差别，因此会造成时序数据匹配时的“Singularities”问题。 归根结底，“Singularities”问题在某种程度上就源于只考虑 Y 轴的值，第一个序列上的一个点可以跟第二个序列上的另一个很远（此处“远”指的是 X 轴的距离/序数）的点匹配起来，加上 DTW 中 warping path 的连续性、单调性条件，造成了时序数据对齐过程中的各种翘曲/扭曲。 DDTW 通过考虑“形状”利用估计时序数据的一阶导数来解决这个问题，而 WDTW 则采用了不同的思路。简单来说，WDTW 选择在计算两个序列上的两个点之间欧氏距离时加上一个 weight，而这个 weight 与两个点之间的 X 轴上的距离有关系。具体如下（p=2）：
如上式，p=2 时为计算两个序列上的两个点 值，则可避免算法将两个距离较大的点匹配在一起。 针对 WDTW，Jeong, Y. S., Jeong, M. K., & Omitaomu, O. A. 等人还提出了一个 logistic weight function 来赋予权重，感兴趣的读者可自行查阅原文。值得一提的是，当 的值极大时，此时的 WDTW 对于 X 轴上距离不同的点惩罚也极大，甚至第 i 个点和第 i-1 个点的匹配也不行，此时的 WDTW 即对应传统的欧氏距离。
总结与补充
综上，本文从只能处理等长数据且容易造成不自然对齐的欧氏距离出发，我们逐步论述了 DTW 出现的原因和重要性。进一步，我们发现传统 DTW 算法带来的 singularities 问题可以在 windowing、slope weighting、step pattern 等方法下得到一定改善。然而，从算法考虑的特征层面出发，为了解决 DTW 算法匹配时序数据时可能存在的 singularities 问题，DDTW 提出考虑更高层次的特征——形状，并利用估计一阶导数来实现。最后，WDTW 显示出它是一个更大的可以包含欧氏距离、传统 DTW 的距离度量框架，同时 WDTW 也通过考虑了时序数据匹配过程中的 phase difference 为解决 singularities 问题提供了另一种思路。 源于距离矩阵的构建，DTW 及其变种的算法复杂度是相同的，均为 。此外，本文所述内容并未涉及 DTW 在大规模数据集检索中的算法加速问题。实际上，在大规模的应用中，过去的研究已经有了很多方法来对 DTW 算法进行加速，如：FastDTW，LB_Keogh 等。 Keogh, E., & Ratanamahatana, C. A. (2005). Exact indexing of dynamic time warping.Knowledge and information systems,7(3), 358-386.
#投 稿 通 道 #
让你的文字被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。
总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读 ，也可以是学术热点剖析 、科研心得 或竞赛经验讲解 等。我们的目的只有一个，让知识真正流动起来。
📝 稿件基本要求：
• 文章确系个人原创作品 ，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注
• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题
• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬 ，具体依据文章阅读量和文章质量阶梯制结算
📬 投稿通道：
• 投稿邮箱： hr@paperweekly.site
• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者
• 您也可以直接添加小编微信（pwbot02 ）快速投稿，备注：姓名-投稿
△长按添加PaperWeekly小编
🔍
现在，在「知乎」 也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」 订阅我们的专栏吧